package SingleLinkedList;

/**
 * 查找两个单链表第一个相交的节点
 *
 * @author Liaorun
 */
public class FindFirstIntersectNode {
    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        // 获取第一个单链表是否有环
        Node loop1 = getLoopNode(head1);
        // 获取第二个单链表是否有环
        Node loop2 = getLoopNode(head2);

        if (loop1 == null && loop2 == null) {
            // 两个无环链表的相交问题
            return noLoop(head1, head2);
        }

        if (loop1 != null && loop2 != null) {
            // 两个有环链表的相交问题
            return bothLoop(head1, loop1, head2, loop2);
        }

        // 一个链表有环一个无环，一定不相交
        return null;
    }

    private static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node cur1 = null;
        Node cur2 = null;

        // 进入环的节点相等
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;
            int n = 0;

            // 链表1，当层无环的处理，计算长度到入环点就停止，不管环部分的节点
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }

            // 链表2，当层无环的处理，计算长度到入环点就停止，不管环部分的节点
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }

            // n  = 单链表1.length - 单链表2.length
            // 谁长，谁的头变成cur1
            cur1 = n > 0 ? head1 : head2;
            // 谁短，谁的头变成cur2
            cur2 = cur1 == head1 ? head2 : head1;

            // 计算两个单链表的长度差
            n = Math.abs(n);

            // 长的单链表先向前走一个距离差
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }

            // 两条链表同时向前走，走到交汇点就跳出
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }

            // 返回两条链条的第一个交汇点
            return cur1;
        } else {
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }

    /**
     * 找到单链表第一个入环节点，如果无环，返回null
     *
     * @param head 头节点
     * @return 有环 第一个入环节点， 无环 null
     */
    private static Node getLoopNode(Node head) {

        if (head == null || head.next == null) {
            return null;
        }

        // 慢指针先走一步
        Node n1 = head.next;
        // 快指针先走2步，防止下面的循环直接不能进入
        Node n2 = head.next.next;

        // 快慢指针相遇跳出，表示存在环
        while (n1 != n2) {
            // 只要快指针走到 null 肯定没有环
            if (n2.next == null || n2.next.next == null) {
                return null;
            }

            // 快指针走2步
            n2 = n2.next.next;
            // 慢指针走1步
            n1 = n1.next;
        }

        // 快指针回到起点
        n2 = head;
        // 快慢指针相遇跳出，表示存在环,且此时都指向入环的第一个节点
        while (n1 != n2) {
            // 快指针走2步
            n2 = n2.next.next;
            // 慢指针走1步
            n1 = n1.next;
        }
        // 返回第一个入环节点
        return n1;
    }

    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }

        Node cur1 = head1;
        Node cur2 = head2;

        int n = 0;
        while (cur1.next != null) {
            n++;
            cur1 = cur1.next;
        }

        while (cur2.next != null) {
            n--;
            cur2 = cur2.next;
        }

        if (cur1 != cur2) {
            return null;
        }

        // n  = 单链表1.length - 单链表2.length
        // 谁长，谁的头变成cur1
        cur1 = n > 0 ? head1 : head2;
        // 谁短，谁的头变成cur2
        cur2 = cur1 == head1 ? head2 : head1;

        // 计算两个单链表的长度差
        n = Math.abs(n);

        // 长的单链表先向前中一个距离差
        while (n != 0) {
            n--;
            cur1 = cur1.next;
        }

        // 两条链表同时向前走，走到交汇点就跳出
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }

        // 返回两条链条的第一个交汇点
        return cur1;
    }
}
